/*
 * @Author: wwssaabb
 * @Date: 2021-12-15 17:18:45
 * @LastEditTime: 2021-12-15 17:36:39
 * @FilePath: \handwritten-code\排序算法\插入排序.js
 */



/* 
  插入排序
  思路：可以当做整理扑克牌一样，将元素一个一个拿出，然后放到自己该在的位置
*/

console.time(1)

function insertionSort(arr) {
  let len = arr.length,
    cur, preIndex
  for (let i = 1; i < len; i++) {
    cur = arr[i]
    preIndex = i - 1
    while (preIndex >= 0 && arr[preIndex] > cur) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = cur
  }
  return arr
}

const arr = [89, 58, 66, 74, 15, 34, 99, 78, 45, 33, 21, 16, 85, 54]
console.log(insertionSort(arr))

console.timeEnd(1)